#include "graph_support/alg_correctness_tests/dinic_alg_tests/GeneratorsCollection.h"

#include <vector>
#include <math.h>
#include <assert.h>
#include <utility>

#include <boost/random.hpp>
#include <boost/shared_ptr.hpp>

#include "graph_support/IGraph.h"
#include "graph_support/attributes/LengthEdgeAttributes.h"
#include "graph_support/impls/wrap_igraph/WrapIGraph.h"

#include "graph_support/alg/shortest_path/Dejkstra.h"
#include "graph_support/alg_correctness_tests/generate_graph/BindGraphOperation.h"
#include "graph_support/alg_correctness_tests/generate_graph/OperationsBsdGenerator.h"
#include "graph_support/decorate/JoinGraph.h"
#include "graph_support/decorate/ConvertGraphAttributes.h"


using namespace dinic_alg_test;
using namespace GRAPH_SUPPORT_NS;
using namespace GRAPH_SUPPORT_NS::attributes;
using namespace GRAPH_SUPPORT_NS::impls;
using namespace GRAPH_SUPPORT_NS::decorate;
using namespace generate_graph;

typedef FlowGraph2Gen::EdgeAttributes FlowEdgeAttributes4Gen;
//typedef IGraph::EdgeAttributesImpl< NFlowAttributes >::Attributes FlowAttributesWrap;
typedef IGraph::EdgeAttributesImpl< FlowEdgeAttributes4Gen >::CpAttributes CpFlowAttributesWrap;

typedef CostFlowGraph2Gen::EdgeAttributes CostFlowEdgeAttributes4Gen;
typedef IGraph::EdgeAttributesImpl< CostFlowEdgeAttributes4Gen >::Attributes ICostFlowEdgeAttributes;
typedef IGraph::EdgeAttributesImpl< CostFlowEdgeAttributes4Gen >::CpAttributes ICostFlowEdgeAttributesImpl;

typedef IGraph::IEdgeAttributesPtr IEdgeAttributesPtr;
typedef FlowEdgeAttributes4Gen::Capacity Capacity;
typedef CostFlowEdgeAttributes4Gen::Cost Cost;


namespace
{

class ImkAttributes
{
public:
	virtual ~ImkAttributes() {}
	virtual IEdgeAttributesPtr mkAttributes( boost::rand48 & randomGenerator ) = 0;
};
// TODO: review: why is it needed
typedef boost::shared_ptr< ImkAttributes > ImkAttributesPtr;

class MKFlowEdgeAttributes4UnitTests : public ImkAttributes
{
public:
	virtual IEdgeAttributesPtr mkAttributes( boost::rand48 & randomGenerator )
	{
		double capacity =
				( double ) ( randomGenerator() % 1000 ) /
				( randomGenerator() % 40 + 100 );
		return IEdgeAttributesPtr(
				new CpFlowAttributesWrap(
						FlowEdgeAttributes4Gen( capacity ) ) );
	}
};

class MKCostFlowEdgeAttributes : public ImkAttributes
{
public:
	virtual IEdgeAttributesPtr mkAttributes( boost::rand48 & randomGenerator )
	{
		double capacity =
				( double ) ( randomGenerator() % 1000 ) /
				( randomGenerator() % 40 + 100 );
		double cost =
				( double ) ( randomGenerator() % 100 ) /
				( randomGenerator() % 40 + 100 );
		cost += capacity / 10;
		cost -= 0.15;
		return IEdgeAttributesPtr(
				new ICostFlowEdgeAttributesImpl(
						CostFlowEdgeAttributesTmpl< double >( capacity, cost ) ) );
	}
};

IGraphGenerator::GraphPtr easyLine(
		const IGraphGenerator::GraphPtr & gptr,
		size_t src,
		size_t dest,
		double lengthMul,
		const ImkAttributesPtr & attributesMaker,
		boost::shared_ptr< int > & randomSeed
) {
	IGraph & gr = * gptr;
	int n = gr.igetVertexCount();
	int length = floor( lengthMul * n );

	boost::rand48 randomGenerator( * randomSeed );
	* randomSeed = randomGenerator();

	std::vector< size_t > candidates;
	for ( int i = 0; i < n; i++ )
	{
		if ( i != src && i != dest )
		{
			candidates.push_back( i );
		}
	}

	size_t pid = src;
	for ( int i = 0; i < length; i++ )
	{
		int pos = randomGenerator() % candidates.size();
		size_t vid = i == length - 1 ?
				dest:
				candidates[pos];
		IEdgeAttributesPtr attributes = attributesMaker->mkAttributes( randomGenerator );
		gr.iaddEdge( pid, vid, attributes );
		pid = vid;
	}

	return gptr;
}

template< typename GrEdgePtrT >
LengthEdgeAttributesTmpl< double > exists4posCap( GrEdgePtrT & eptr )
{
	typedef LengthEdgeAttributesTmpl< double > ResultEdgeAttributes;

	if ( & ( eptr->getAttributes() ) == NULL )
	{
		return LengthEdgeAttributesTmpl< double >::getINFLength();
	}
	if ( eptr->getAttributes().getCapacity() > 1e-5 )
	{
		return ResultEdgeAttributes( 1.0 );
	}
	return ResultEdgeAttributes::getINFLength();
}

bool isReachable(
		IGraph & gr,
		size_t a,
		size_t b
) {
	using namespace impls::wrap_igraph;
	using namespace alg::shortest_path;

	// TODO: graph name
	typedef WrapIGraph< FlowEdgeAttributes4Gen > WFGraph;
	typedef WrapIGraph< CostFlowEdgeAttributes4Gen > WCFGraph;
	typedef ConvertGraphAttributesTmpl< WFGraph, LengthEdgeAttributesTmpl< double > > WF2LGraph;
	typedef ConvertGraphAttributesTmpl< WCFGraph, LengthEdgeAttributesTmpl< double > > WCF2LGraph;
	typedef JoinGraphTmpl< WF2LGraph, WCF2LGraph > JCFFGraph;

	WFGraph wfgr( gr );
	WCFGraph wcfgr( gr );
	WF2LGraph wf2lgr( wfgr, & exists4posCap< WFGraph::GrEdgePtr > );
	WCF2LGraph wcf2lgr( wcfgr, & exists4posCap< WCFGraph::GrEdgePtr > );
	JCFFGraph jcffgr( wf2lgr, wcf2lgr );
	Dejkstra< JCFFGraph > dejkstra( jcffgr );
	dejkstra( a );

	return dejkstra.getDistance( b ) <
			JCFFGraph::EdgeAttributes::getINFLength();
}

template< typename EdgeAttributesT > // TODO: name
std::pair< EdgeAttributesT &, IEdgeAttributesPtr > getAttrs( IGraph::IEdgeIterator & eit )
{
	typedef typename IGraph::EdgeAttributesImpl< EdgeAttributesT >::IAttributes IEdgeAttributes;
	IEdgeAttributesPtr attrsptr = eit.getEdgeAttributes();
	IEdgeAttributes * awrap = dynamic_cast< IEdgeAttributes * >( attrsptr.get() );
	assert( awrap );
	return std::pair< EdgeAttributesT &, IEdgeAttributesPtr >( * awrap->get(), attrsptr );
}

template< typename EdgeAttributesT >
const std::vector< int > collectCapDestinations(
		IGraph & gr,
		size_t src,
		size_t dest,
		double eps = 1e-5
) {
	std::vector< int > result;

	int n = gr.igetVertexCount();

	IGraph::IEdgeIteratorPtr eitPtr = gr.igetOutEdgesIterator();
	IGraph::IEdgeIterator & eit = * eitPtr;
	for ( int i = 0; i < n; i++ )
	{
		if ( i == src || i == dest )
		{
			continue;
		}
		for ( gr.igetOutEdgesIterator( i, eit ); eit.notFinished(); eit.next() )
		{
			bool isGood =
					eit.getDestination() != src &&
					eit.getDestination() != dest &&
					getAttrs< EdgeAttributesT >( eit ).first.getCapacity() > eps;
			if ( isGood )
			{
				result.push_back( eit.getDestination() );
			}
		}
	}

	return result;
}

template< typename EdgeAttributesT >
const std::vector< size_t > collectCapPath(
		IGraph & gr,
		size_t a,
		size_t src,
		size_t dest,
		double eps = 1e-5
) {
	std::vector< size_t > result;
	result.push_back( a );

	std::vector< char > visitedBuf( gr.igetVertexCount(), ( char ) false );
	bool * visited = ( bool * ) & visitedBuf[0];
	visited[src] = true;
	visited[dest] = true;

	size_t i = a;
	// TODO: dfs here
	IGraph::IEdgeIteratorPtr eitPtr = gr.igetOutEdgesIterator();
	IGraph::IEdgeIterator & eit = * eitPtr;
	while ( ! visited[i] )
	{
		visited[i] = true;
		for ( gr.igetOutEdgesIterator( i, eit ); eit.notFinished(); eit.next() )
		{
			size_t nextCandVid = eit.getDestination();
			if ( getAttrs< EdgeAttributesT >( eit ).first.getRemainCapacity() > eps && ! visited[nextCandVid] )
			{
				result.push_back( nextCandVid );
				i = nextCandVid;
				break;
			}
		}
	}

	return result;
}

template< typename EdgeAttributesT >
IGraphGenerator::GraphPtr moveBackPath(
		const IGraphGenerator::GraphPtr & gptr,
		size_t src,
		size_t dest,
		double lengthMul,
		const ImkAttributesPtr & attributesMaker,
		boost::shared_ptr< int > & randomSeed
) {
	IGraph & gr = * gptr;

	double eps = 1e-5;
	boost::rand48 randomGenerator( * randomSeed );
	* randomSeed = randomGenerator();

	const std::vector< int > acandidates = collectCapDestinations< EdgeAttributesT >( gr, src, dest, eps );
	if ( acandidates.empty() )
	{
		return gptr;
	}
	int apos = randomGenerator() % acandidates.size();
	size_t a = acandidates[apos];

	const std::vector< size_t > bcandidates = collectCapPath< EdgeAttributesT >( gr, a, src, dest, eps );
	assert( ! bcandidates.empty() );
	size_t bpos = randomGenerator() % bcandidates.size();
	size_t b = bcandidates[bpos];
	assert( isReachable( gr, a, b ) );

	easyLine( gptr, src, b, lengthMul / 2, attributesMaker, randomSeed );
	easyLine( gptr, a, dest, lengthMul / 2, attributesMaker, randomSeed );

	return gptr;
}

template< typename EdgeAttributesT >
IGraphGenerator::GraphPtr leastCut(
		const IGraphGenerator::GraphPtr & gptr,
		size_t src,
		size_t dest,
		double reduceCapacityMul,
		boost::shared_ptr< int > & randomSeed
) {
	IGraph & gr = * gptr;
	int n = gr.igetVertexCount();
	boost::rand48 randomGenerator( * randomSeed );
	* randomSeed = randomGenerator();

	char UNKNOWN = 0;
	char SRC_PART = 1;
	char DEST_PART = 2;
	std::vector< char > vid2partBuf( n, UNKNOWN );
	char * vid2part = & vid2partBuf[0];
	vid2part[src] = SRC_PART;
	vid2part[dest] = DEST_PART;

	for ( int i = 0; i < n; i++ )
	{
		if ( vid2part[i] == UNKNOWN )
		{
			vid2part[i] = 1 + ( randomGenerator() & 1 );
		}
	}

	IGraph::IEdgeIteratorPtr eitPtr = gr.igetOutEdgesIterator();
	IGraph::IEdgeIterator & eit = * eitPtr;
	for ( int i = 0; i < n; i++ )
	{
		if ( vid2part[i] != SRC_PART )
		{
			continue;
		}
		for ( gr.igetOutEdgesIterator( i, eit ); eit.notFinished(); eit.next() )
		{
			size_t d = eit.getDestination();
			if ( vid2part[d] != DEST_PART )
			{
				continue;
			}
			std::pair< EdgeAttributesT &, IEdgeAttributesPtr > attrs = getAttrs< EdgeAttributesT >( eit );

			Capacity newCap = attrs.first.getCapacity() * reduceCapacityMul;
			attrs.first.setCapacity( newCap );
			assert( dynamic_cast< typename IGraph::EdgeAttributesImpl< EdgeAttributesT >::IAttributes * >( eit.getEdgeAttributes()
					.get() )->get()->getCapacity() == newCap );
		}
	}

	return gptr;
}

// TODO: unite all "cut"-s
IGraphGenerator::GraphPtr expensiveCut(
		const IGraphGenerator::GraphPtr & gptr,
		size_t src,
		size_t dest,
		double costAdd,
		double costMul,
		boost::shared_ptr< int > & randomSeed
) {
	IGraph & gr = * gptr;
	int n = gr.igetVertexCount();
	boost::rand48 randomGenerator( * randomSeed );
	* randomSeed = randomGenerator();

	char UNKNOWN = 0;
	char SRC_PART = 1;
	char DEST_PART = 2;
	std::vector< char > vid2partBuf( n, UNKNOWN );
	char * vid2part = & vid2partBuf[0];
	vid2part[src] = SRC_PART;
	vid2part[dest] = DEST_PART;

	for ( int i = 0; i < n; i++ )
	{
		if ( vid2part[i] == UNKNOWN )
		{
			vid2part[i] = 1 + ( randomGenerator() & 1 );
		}
	}

	IGraph::IEdgeIteratorPtr eitPtr = gr.igetOutEdgesIterator();
	IGraph::IEdgeIterator & eit = * eitPtr;
	for ( int i = 0; i < n; i++ )
	{
		if ( vid2part[i] != SRC_PART )
		{
			continue;
		}
		for ( gr.igetOutEdgesIterator( i, eit ); eit.notFinished(); eit.next() )
		{
			size_t d = eit.getDestination();
			if ( vid2part[d] != DEST_PART )
			{
				continue;
			}
			std::pair< CostFlowEdgeAttributes4Gen &, IEdgeAttributesPtr > attrs = getAttrs< CostFlowEdgeAttributes4Gen >( eit );

			Capacity newCost = costAdd + attrs.first.getCost() * costMul;
			attrs.first.setCost( newCost );
			assert( dynamic_cast< ICostFlowEdgeAttributes * >( eit.getEdgeAttributes().get() )->get()
					->getCost() == newCost );
		}
	}

	return gptr;
}

IGraphGenerator::GraphPtr negativeCycle(
		const IGraphGenerator::GraphPtr & gptr,
		size_t src,
		size_t dest,
		double lengthMul,
		boost::shared_ptr< int > & randomSeed
) {
	IGraph & gr = * gptr;
	int n = gr.igetVertexCount();
	int length = floor( lengthMul * n );

	boost::rand48 randomGenerator( * randomSeed );
	* randomSeed = randomGenerator();

	std::vector< size_t > candidates;
	for ( int i = 0; i < n; i++ )
	{
		if ( i != src && i != dest )
		{
			candidates.push_back( i );
		}
	}

	size_t pid = Graph::NOT_A_VERTEX_ID;
	size_t fid = Graph::NOT_A_VERTEX_ID;
	double cycleCost = 0;
	for ( int i = 0; i < length; i++ )
	{
		int pos = randomGenerator() % candidates.size();
		size_t vid = i == length - 1 ?
				fid :
				candidates[pos];
		if ( fid == Graph::NOT_A_VERTEX_ID )
		{
			fid = vid;
			pid = vid;
			continue;
		}
		double capacity = 2 +
				( double ) ( randomGenerator() % 1000 ) /
				( randomGenerator() % 100 + 1 );
		double cost =
				( double ) ( randomGenerator() % 100 ) /
				( randomGenerator() % 50 + 70 );
		cost -= 0.8;
		cycleCost += cost;
		CostFlowEdgeAttributes4Gen attributes( capacity, cost );
		gr.iaddEdge( pid, vid,
			IEdgeAttributesPtr(
					new ICostFlowEdgeAttributesImpl(
							CostFlowEdgeAttributes4Gen( capacity, cost ) ) ) );
		pid = vid;
	}

	return gptr;
}

}

std::vector< TestCase > dinic_alg_test::getTestCases4Dinic()
{
	boost::shared_ptr< int > randomSeed( new int[1] );
	* randomSeed = 12345;
	ImkAttributesPtr attributesMaker( new MKFlowEdgeAttributes4UnitTests() );
	OperationsBsdGenerator::NewGraphFn newGrFn = & NewGraphFnTmpl< FlowGraph2Gen >;

	std::vector< TestCase > testCases;

	{ const char * name = "Easy lines small";
	int src = 0;
	int dest = 1;
	std::vector< IGraphOperationPtr > operations;
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 10 ) );
	testCases.push_back( TestCase( IGraphGeneratorPtr(
			new OperationsBsdGenerator( name, 100, operations, newGrFn, true ) ), 100 ) );
	}
	{ const char * name = "Easy lines BIG";
	int src = 0;
	int dest = 1;
	std::vector< IGraphOperationPtr > operations;
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 15 ) );
	testCases.push_back( TestCase( IGraphGeneratorPtr(
			new OperationsBsdGenerator( name, 300, operations, newGrFn, true ) ), 10 ) );
	}
	{ const char * name = "Lines & mv back small";
	int src = 0;
	int dest = 1;
	std::vector< IGraphOperationPtr > operations;
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 7 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< FlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 35 ) );
	testCases.push_back( TestCase( IGraphGeneratorPtr(
			new OperationsBsdGenerator( name, 100, operations, newGrFn, true ) ), 100 ) );
	}
	{ const char * name = "Lines & mv back BIG";
	int src = 0;
	int dest = 1;
	std::vector< IGraphOperationPtr > operations;
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 10 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< FlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 80 ) );
	testCases.push_back( TestCase( IGraphGeneratorPtr(
			new OperationsBsdGenerator( name, 250, operations, newGrFn, true ) ), 10 ) );
	}
	{ const char * name = "The least cut small";
	int src = 0;
	int dest = 1;
	std::vector< IGraphOperationPtr > operations;
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 20 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< FlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 10 ) );

	// CUT - veru critical
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< FlowEdgeAttributes4Gen >, _1, src, dest, 0.1, _2 ), randomSeed, 2 ) );

	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< FlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 3 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 5 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< FlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 3 ) );
	// CUT not critical
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< FlowEdgeAttributes4Gen >, _1, src, dest, 0.5, _2 ), randomSeed, 5 ) );

	testCases.push_back( TestCase( IGraphGeneratorPtr(
			new OperationsBsdGenerator( name, 100, operations, newGrFn, true ) ), 100 ) );
	}
	{ const char * name = "The least cut BIG";
	int src = 0;
	int dest = 1;
	std::vector< IGraphOperationPtr > operations;
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 30 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< FlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 15 ) );

	// CUT - veru critical
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< FlowEdgeAttributes4Gen >, _1, src, dest, 0.3, _2 ), randomSeed, 5 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< FlowEdgeAttributes4Gen >, _1, src, dest, 0.1, _2 ), randomSeed, 2 ) );

	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< FlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 5 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 8 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< FlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 5 ) );
	// CUT not critical
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< FlowEdgeAttributes4Gen >, _1, src, dest, 0.5, _2 ), randomSeed, 7 ) );

	testCases.push_back( TestCase( IGraphGeneratorPtr(
			new OperationsBsdGenerator( name, 250, operations, newGrFn, true ) ), 10 ) );
	}

	return testCases;
}

std::vector< TestCase > dinic_alg_test::getTestCases4MinCostFlow()
{
	boost::shared_ptr< int > randomSeed( new int[1] );
	* randomSeed = 12345;
	ImkAttributesPtr attributesMaker( new MKCostFlowEdgeAttributes() );
	OperationsBsdGenerator::NewGraphFn newGrFn = & NewGraphFnTmpl< CostFlowGraph2Gen >;

	std::vector< TestCase > testCases;

	{ const char * name = "Lines & mv back BIG";
	int src = 0;
	int dest = 1;
	std::vector< IGraphOperationPtr > operations;
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 15 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 7 ) );
	testCases.push_back( TestCase( IGraphGeneratorPtr(
			new OperationsBsdGenerator( name, 100, operations, newGrFn, true ) ), 10 ) );
	}
	{ const char * name = "Lines & mv back & the least cut & neg cyc small";
	int src = 0;
	int dest = 1;
	std::vector< IGraphOperationPtr > operations;
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 15 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 7 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.1, _2 ), randomSeed, 3 ) );

	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 3 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.5, _2 ), randomSeed, 3 ) );

	operations.push_back( MKBindGraphOperation(
			boost::bind( negativeCycle, _1, src, dest, 0.2, _2 ), randomSeed, 5 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.3, _2 ), randomSeed, 4 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( negativeCycle, _1, src, dest, 0.2, _2 ), randomSeed, 3 ) );

	testCases.push_back( TestCase( IGraphGeneratorPtr(
			new OperationsBsdGenerator( name, 40, operations, newGrFn, true ) ), 20 ) );
	}
	{ const char * name = "Lines & mv back & the least cut & neg cyc BIG";
	int src = 0;
	int dest = 1;
	std::vector< IGraphOperationPtr > operations;
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 15 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 7 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.1, _2 ), randomSeed, 3 ) );

	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 3 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.5, _2 ), randomSeed, 3 ) );

	operations.push_back( MKBindGraphOperation(
			boost::bind( negativeCycle, _1, src, dest, 0.2, _2 ), randomSeed, 5 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.3, _2 ), randomSeed, 4 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( negativeCycle, _1, src, dest, 0.2, _2 ), randomSeed, 3 ) );

	testCases.push_back( TestCase( IGraphGeneratorPtr(
			new OperationsBsdGenerator( name, 90, operations, newGrFn, true ) ), 3 ) );
	}
	{ const char * name = "Lines & mv back & the least cut & neg cyc && expensive cut small";
	int src = 0;
	int dest = 1;
	std::vector< IGraphOperationPtr > operations;
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 15 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 7 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.1, _2 ), randomSeed, 3 ) );

	operations.push_back( MKBindGraphOperation(
			boost::bind( expensiveCut, _1, src, dest, 1.5, 2.0, _2 ), randomSeed, 5 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( negativeCycle, _1, src, dest, 0.2, _2 ), randomSeed, 5 ) );

	testCases.push_back( TestCase( IGraphGeneratorPtr(
			new OperationsBsdGenerator( name, 50, operations, newGrFn, true ) ), 20 ) );
	}
	{ const char * name = "Lines & mv back & the least cut & neg cyc && expensive cut BIG";
	int src = 0;
	int dest = 1;
	std::vector< IGraphOperationPtr > operations;
	operations.push_back( MKBindGraphOperation(
			boost::bind( easyLine, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 15 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( moveBackPath< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.3, attributesMaker, _2 ), randomSeed, 7 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( leastCut< CostFlowEdgeAttributes4Gen >, _1, src, dest, 0.1, _2 ), randomSeed, 3 ) );

	operations.push_back( MKBindGraphOperation(
			boost::bind( expensiveCut, _1, src, dest, 1.5, 2.0, _2 ), randomSeed, 5 ) );
	operations.push_back( MKBindGraphOperation(
			boost::bind( negativeCycle, _1, src, dest, 0.2, _2 ), randomSeed, 5 ) );

	testCases.push_back( TestCase( IGraphGeneratorPtr(
			new OperationsBsdGenerator( name, 120, operations, newGrFn, true ) ), 5 ) );
	}

	return testCases;
}
